#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <string>
#include <map>
#include <algorithm>
#include <functional>
#include <list>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	
};

class Solution1 {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int sz = q.size(); bool flag = false;
            while (sz--)
            {
                TreeNode* f = q.front();
                q.pop();
                TreeNode* l = f->left; TreeNode* r = f->right;
                if (flag && (l || r)) return false;
                if (!l && r) return false;
                else if (!(l && r)) flag = true;
                if (l) q.push(l);
                if (r) q.push(r);
            }
            if (flag) break;
        }
        while (!q.empty())
        {
            TreeNode* f = q.front();
            q.pop();
            if (f->left || f->right) return false;
        }

        return true;
    }
};

class Solution2
{
public:
    void solve()
    {
        vector<int> cost;
        int in;
        while (cin >> in)
        {
            cost.push_back(in);
            if (getchar() == EOF) break;
        }
        int n = cost.size();
        vector<int> dp(n);
        dp[0] = cost[0]; dp[1] = cost[1];
        for (int i = 2; i < n; ++i)
        {
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        cout << min(dp[n - 1], dp[n - 2]);
    }
};

class Solution3 {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int sz = m + n - 1;
        --m; --n;
        while (m >= 0 && n >= 0)
        {
            if (nums1[m] > nums2[n])
                nums1[sz] = nums1[m--];
            else
                nums1[sz] = nums2[n--];
            --sz;
        }
        while (n >= 0) nums1[sz--] = nums2[n--];
    }
};

class Solution4 {
public:
    int removeElement(vector<int>& nums, int val) {
        int res = 0;
        for (int x : nums)
            if (x != val)
                nums[res++] = x;
        return res;
    }
};

class Solution5 {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) return n;
        int f = 2, s = 2;
        while (f < n)
        {
            if (nums[s - 2] != nums[f])
            {
                nums[s] = nums[f];
                ++s;
            }
            ++f;
        }
        return s;
    }
};

class Solution6 {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        vector<int> nnums(n);
        for (int i = 0; i < n; ++i)
        {
            nnums[(i + k) % n] = nums[i];
        }
        nums.swap(nnums);
    }
};

class Solution7
{
public:
    void solve()
    {
        int n, k, m;
        cin >> n >> k >> m;
        list<int> l;
        for (int i = 0; i < n; ++i)
            l.push_back(i);
        auto it = l.begin();
        while (k--) ++it;
        while (l.size() > 1)
        {
            int tmp = m;
            int cnt = 1;
            while (cnt < m)
            {
                ++it;
                if (it == l.end()) it = l.begin();
                ++cnt;
            }
            auto cur = it;
            ++it;
            if (it == l.end()) it = l.begin();
            l.erase(cur);
        }
        cout << *l.begin();
    }
};

class Solution8 {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), mxpos = 0, end = 0, step = 0;
        for (int i = 0; i < n - 1; ++i)
        {
            mxpos = max(mxpos, i + nums[i]);
            if (i == end)
            {
                end = mxpos;
                ++step;
            }
        }
        return step;
    }
};

class RandomizedSet {
private:
    vector<int> nums;
    unordered_map<int, int> mp;
public:
    RandomizedSet() { srand((unsigned int)time(nullptr)); }

    bool insert(int val) {
        auto it = mp.find(val);
        if (it == mp.end())
        {
            nums.push_back(val);
            mp[val] = nums.size() - 1;
            return true;
        }
        return false;
    }

    bool remove(int val) {
        auto it = mp.find(val);
        if (it == mp.end())
            return false;
        mp[nums.back()] = it->second;
        swap(nums[it->second], nums.back());
        mp.erase(it);
        nums.pop_back();
        return true;
    }

    int getRandom() {
        int r = rand() % nums.size();
        return nums[r];
    }
};

class Solution9 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> lmul(n), rmul(n);
        lmul[0] = nums[0]; rmul[n - 1] = nums[n - 1];
        for (int i = 1; i < n; ++i)
        {
            lmul[i] = lmul[i - 1] * nums[i];
            rmul[n - 1 - i] = rmul[n - i] * nums[n - 1 - i];
        }
        vector<int> res(n);
        res[0] = rmul[1]; res[n - 1] = lmul[n - 2];
        for (int i = 1; i < n - 1; ++i)
            res[i] = lmul[i - 1] * rmul[i + 1];
        return res;
    }
};

int main()
{

    return 0;
}